/*
 * @lc app=leetcode.cn id=130 lang=typescript
 *
 * [130] 被围绕的区域
 */

// @lc code=start
/**
 Do not return anything, modify board in-place instead.
 */

//  思路：并查集
//  四边上的 O ，以及与边 O 相连的 O 不会被替换
//  设置 dummy ，让四边上的 O 和与其相连的 O 与 dummy 联通
//  最后遍历所有不与 dummy 联通的 O 并进行替换
//  思路：https://labuladong.github.io/algo/2/18/37/

function solve(board: string[][]): void {
    if (board.length === 0) return
    const m = board.length, n = board[0].length
    // 初始化并查集
    const uf = new UF(m * n + 1)
    const dummy = m * n
    // 将首列和末列的 O 与 dummy 联通
    for (let i = 0; i < m; i++) {
        if (board[i][0] === 'O') uf.union(i * n, dummy)
        if (board[i][n - 1] === 'O') uf.union(i * n + n - 1, dummy)
    }
    // 将首行和末行的 O 与 dummy 连通
    for (let j = 0; j < n; j++) {
        if (board[0][j] === 'O') uf.union(j, dummy)
        if (board[m - 1][j] === 'O') uf.union(n * (m - 1) + j, dummy)
    }

    // 方向数组
    const dirs = [[1, 0], [0, 1], [0, -1], [-1, 0]]
    for (let i = 1; i < m - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            if (board[i][j] === 'O') {
                // 将此 O 与上下左右的 O 连通
                for (let k = 0; k < 4; k++) {
                    const x = i + dirs[k][0]
                    const y = j + dirs[k][1]
                    if (board[x][y] === 'O') {
                        uf.union(x * n + y, i * n + j)
                    }
                }
            }
        }
    }
    // 所有不和 dummy 连通的 O，都要被替换
    for (let i = 1; i < m - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            if (!uf.connnect(dummy, i * n + j)) {
                board[i][j] = 'X'
            }
        }
    }
};

class UF {
    count: number
    parent: number[]
    size: number[]
    constructor(n: number) {
        this.count = n
        this.parent = new Array(n).fill(0)
        this.size = new Array(n).fill(1)
        for (let i = 0; i < n; i++) {
            this.parent[i] = i
        }
    }
    // 返回x的根节点
    find(x: number): number {
        while (this.parent[x] !== x) {
            // 路径压缩
            this.parent[x] = this.parent[this.parent[x]]
            x = this.parent[x]
        }
        return x
    }
    // 将p、q联通
    union(p: number, q: number) {
        const rootP = this.find(p)
        const rootQ = this.find(q)
        if (rootP === rootQ) return
        if (this.size[rootP] > this.size[rootQ]) {
            this.parent[rootQ] = rootP
            this.size[rootP] += this.size[rootQ]
        } else {
            this.parent[rootP] = rootQ
            this.size[rootQ] += this.size[rootP]
        }
        this.count--
    }
    // 判断p、q是否联通
    connnect(p: number, q: number): boolean {
        const rootP = this.find(p)
        const rootQ = this.find(q)
        return rootP === rootQ
    }
}

// @lc code=end

const board = [["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"]]
solve(board)
console.log(board)

